/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-islands-ii
   @Language: C++
   @Datetime: 19-03-27 16:45
   */

class Solution {
	int find(vector<int> &ufset, int p){
		if(ufset[p]==p) return p;
		return find(ufset, ufset[p]);
	}
public:
	/**
	 * @param n: An integer
	 * @param m: An integer
	 * @param operators: an array of point
	 * @return: an integer array
	 */
	vector<int> numIslands2(int n, int m, vector<Point> &operators) {
		// write your code here
		vector<int> ufset(n*m,-1), v(operators.size(),0);
		vector<pair<int,int> > direct={{1,0},{0,1},{-1,0},{0,-1}};
		for(int sum=0, i=0; i<operators.size(); ++i){
			int x=operators[i].x, y=operators[i].y;
			if (ufset[x*m+y]!=-1){
				v[i]=sum;
				continue;
			}
			ufset[x*m+y]=x*m+y;
			for(const auto &d:direct){
				int p=(x+d.first)*m+y+d.second;
				if(x+d.first>=0 && x+d.first<n 
						&& y+d.second>=0 && y+d.second<m
						&& ufset[p]!=-1) {
					int f=find(ufset,p);
					ufset[f]=x*m+y;
					if (f!=x*m+y) --sum;
				}
			}
			v[i]=++sum;
		}
		return v;
	}
};
